//
// Created by wdq on 22-9-22.
//
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct RadixSort {
    int radix;
    vector<vector<int>> buckets;

    explicit RadixSort(int radix) {
        this->radix = radix;
        buckets.resize(radix);

    }

    void collect(int nums[]) {
        int index = 0;
        for (auto &bucket: buckets) {
            int j = 0;
            while (j < int(bucket.size())) {
                nums[index++] = bucket[j++];
            }
        }
    }

    int getIndex(int num, int r) {
        r = int(log10(r));
        string temp = to_string(num);
        return temp.length() >= r + 1 ? temp[temp.length() - 1 - r] - '0' : 0;
    }

    void distribute(int nums[], int length, int temp) {

        buckets.clear();
        buckets.resize(radix);
        for (int i = 0; i < length; i++) {
            buckets[getIndex(nums[i], temp)].emplace_back(nums[i]);
        }

    }

    int getMaxRadix(int nums[], int length) {
        int temp = INT32_MIN;
        for (int i = 0; i < length; i++) {
            temp = max(nums[i], temp);
        }
        return int(to_string(temp).length());
    }

    void sort(int nums[], int length) {
        int count = getMaxRadix(nums, length);
        int temp = 1;
        for (int i = 0; i < count; i++) {
            distribute(nums, length, temp);
            collect(nums);
            temp *= radix;

        }

    }


};

int main() {

    int nums[] = {2, 6, 1, 56, 4546,25, 67, 89, 5, 3, 3,102};
    printf("nums: ");
    for (auto &i: nums) {
        printf("%-4d ", i);
    }
    printf("\n");
    auto radixSort = RadixSort(10);
    radixSort.sort(nums, sizeof(nums) / sizeof(int));

    printf("sorting..........................\n");
    printf("nums: ");
    for (auto &i: nums) {
        printf("%-4d ", i);
    }
    printf("\n");
    return 0;
}